package Alibaba;

/**
 * @author zhangmin
 * @create 2022-01-21 16:46
 *
 * 718. 最长重复子数组
 * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
 * 1、dp：dp[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀，那么答案即为所有 dp[i][j] 中的最大值。
 *     如果 A[i] == B[j]，那么 dp[i][j] = dp[i + 1][j + 1] + 1，否则 dp[i][j] = 0。
 */
public class findLength718 {
    public int findLength(int[] nums1, int[] nums2) {
        int n1=nums1.length,n2=nums2.length;
        int[][] dp=new int[n1+1][n2+1];
        int res=0;
        for (int i = n1-1; i >=0 ; i--) {
            for (int j = n2-1; j >=0 ; j--) {
                dp[i][j]=nums1[i]==nums2[j]?dp[i+1][j+1]+1:0;
                res=Math.max(dp[i][j],res);
            }
        }
        return res;
    }
}
